package xyz.scootaloo.oj.offer;

import org.junit.Test;

import java.util.HashMap;
import java.util.Map;

/**
 * @author flutterdash@qq.com
 * @since 2021/4/12 21:01
 */
public class P35 {

    public Node copyRandomList(Node head) {
        if (head == null)
            return null;

        Map<Node, Node> map = new HashMap<>();
        Node pointer = head;
        while (pointer != null) {
            map.put(pointer, new Node(pointer.val));
            pointer = pointer.next;
        }

        Node vHead, rHead;
        vHead = rHead = new Node(-1);
        pointer = head;
        while (pointer != null) {
            Node current = map.get(pointer);
            Node random = pointer.random;
            if (random != null)
                current.random = map.get(random);
            vHead.next = current;
            vHead = vHead.next;
            pointer = pointer.next;
        }

        return rHead.next;
    }

    @Test
    public void testFunc() {
        Node node7 = new Node(7);
        Node node13 = new Node(13);
        Node node11 = new Node(11);
        Node node10 = new Node(10);
        Node node1 = new Node(1);

        node7.next = node13;

        node13.next = node11;
        node13.random = node7;

        node11.next = node10;
        node11.random = node1;

        node10.next = node1;
        node10.random = node11;

        node1.random = node7;

        Node root = copyRandomList(node7);
        System.out.println(root);
    }

    private static class Node {
        int val;
        Node next;
        Node random;

        public Node(int val) {
            this.val = val;
            this.next = null;
            this.random = null;
        }
    }

}
